江南白衣 - 分布式Unique ID的生成方法一览
授权声明
本文转载自战略合作伙伴春天的旁边（jnby1978）
作者介绍
江南白衣的Java后端开发，唯品会基础架构，微服务实践的日常。
第33篇架构好文：3482字 |6分钟阅读
前言
分布式的Unique ID的用途如此广泛，从业务对象Id到服务化体系里分布式调用链的TraceId，本文总结了林林总总的各种生成算法。
对于UID的要求，一乐那篇《业务系统需要什么样的ID生成器》的提法很好： 唯一性，时间相关，粗略有序，可反解，可制造。
发号器
_____
我接触的最早的Unique ID，就是Oracle的自增ID。
特点是准连续的自增数字，为什么说是准连续？因为性能考虑，每个Client一次会领20个ID回去慢慢用，用完了再来拿。另一个Client过来，拿的就是另外20个ID了。
新浪微博里，Tim用Redis做相同的事情，Incr一下拿一批ID回去。如果有多个数据中心，那就拿高位的几个bit来区分。
只要舍得在总架构里增加额外Redis带来的复杂度，一个64bit的long就够表达了，而且不可能有重复ID。
批量是关键，否则每个ID都远程调用一次谁也吃不消。
UUID
_____
2.1 概述
Universally Unique IDentifier(UUID)，有着正儿八经的RFC4122规范 ，是一个128bit的数字，也可以表现为32个16进制的字符，中间用"-"分割。
- 时间戳＋UUID版本号：分三段占16个字符(60bit+4bit)，
- Clock Sequence号与保留字段：占4个字符(13bit＋3bit)，
- 节点标识：占12个字符(48bit)，
比如：f81d4fae-7dec-11d0-a765-00a0c91e6bf6
实际上，UUID一共有多种算法，能用于TraceId的是：
version1: 基于时间的算法
version4: 基于随机数的算法
2.2 version 4 基于随机数的算法
先说Version4，这是最暴力的做法，也是JDK里的算法，不管原来各个位的含义了，除了少数几个位必须按规范来填，其余全部用随机数表达。
JDK里的实现，用 SecureRandom生成了16个随机的Byte，用2个long来存储。记得加-Djava.security.egd=file:/dev/./urandom，详见《SecureRandom的江湖偏方与真实效果》
2.3 version 1基于时间的算法
然后是Version1，严格守着原来各个位的规矩：
时间戳：因为时间戳有满满的64bit，所以可以尽情花，以100纳秒为1，从1582年10月15日算起(能撑3655年，真是位数多给烧的，1582年起头有意思么)
顺序号：这16bit则仅用于避免前面的节点标示改变（如网卡改了），时钟系统出问题（如重启后时钟快了慢了），让它随机一下避免重复。
节点标识：48bit，一般用MAC地址表达，如果有多块网卡就随便用一块。如果没网卡，就用随机数凑数，或者拿一堆尽量多的其他的信息，比如主机名什么的，拼在一起再hash一把。
但这里的顺序号并不是我们想象的自增顺序号，而是一个一次性的随机数，所以如果两个请求在同100个纳秒发生时。
还有这里的节点标识只在机器级别，没考虑过一台机器上起了两个进程。
所以严格的Version1没人实现，接着往下看各个变种吧。
Version1变种-Hibernate
_____
Hibernate的CustomVersionOneStrategy.java，解决了之前version 1的两个问题
时间戳(6bytes, 48bit)：毫秒级别的，从1970年算起，能撑8925年....
顺序号(2bytes, 16bit, 最大值65535): 没有时间戳过了一毫秒要归零的事，各搞各的，short溢出到了负数就归0。
机器标识(4bytes 32bit): 拿localHost的IP地址，IPV4呢正好4个byte，但如果是IPV6要16个bytes，就只拿前4个byte。
进程标识(4bytes 32bit)： 用当前时间戳右移8位再取整数应付，不信两条线程会同时启动。
顺序号也不再是一次性的随机数而是自增序列了。
节点标识拆成机器和进程两个字段，增加了从时间戳那边改变精度节约下来的16bit。另外节点标识这64bit（1个Long）总是不变，节约了生成UID的时间。
Version1变种-MongoDB
_____
MongoDB java driver的ObjectId.java
时间戳(4 bytes 32bit): 是秒级别的，从1970年算起，能撑136年。
自增序列(3bytes 24bit, 最大值一千六百万)： 是一个从随机数开始（机智）的Int不断加一，也没有时间戳过了一秒要归零的事，各搞各的。因为只有3bytes，所以一个4bytes的Int还要截一下后3bytes。
机器标识(3bytes 24bit): 将所有网卡的Mac地址拼在一起做个HashCode，同样一个int还要截一下后3bytes。搞不到网卡就用随机数混过去。
进程标识(2bytes 16bits)：从JMX里搞回来到进程号，搞不到就用进程名的hash或者随机数混过去。
可见，MongoDB的每一个字段设计都比Hibernate的更合理一点，时间戳是秒级别的，自增序列变长了，进程标识变短了。总长度也降到了12 bytes 96bit。
但如果果用64bit长的Long来保存有点不上不下的，只能表达成byte数组或16进制字符串。
Twitter的snowflake派号器
_____
snowflake也是一个派号器，基于Thrift的服务，不过不是用redis简单自增，而是类似UUID version1，也是只有一个 64bit的long，所以IdWorker里紧巴巴的分配：
时间戳(42bit) 自从2012年以来(比那些从1970年算起的会过日子)的毫秒数，能撑139年。
自增序列(12bit，最大值4096), 毫秒之内的自增，过了一毫秒要重新置0
DataCenter ID (5 bit, 最大值32），配置值，派号器可能在多个机房。
Worker ID ( 5 bit, 最大值32)，配置值，因为是派号器的id，所以一个数据中心里最多32个派号器就够了，还会在ZK里做下注册。
可见，因为是中央派号器，把至少40bit的节点标识都省出来了，换成10bit的派号器标识。所以整个UID能够只用一个Long表达。
另外，这种派号器，client每次只能一个ID，不能批量取，所以额外增加的延时是问题。
扩展阅读
_____
《细聊分布式ID生成方法》
《生成全局唯一ID的3个思路，来自一个资深架构师的总结》
延伸问题，不用派号器，用Long如何搞定UUID？
_____
这是我们服务化框架一开始的选择问题，TraceID设为了Long，又不用派号器的话，怎么办？
从UUID的128位压缩到Long的64位，又不用中央派号器而是本地生成，最难还是怎么来区分本地的机器＋进程号。
思路一，压缩其他字段，留足够多的长度来做机器＋进程号标识
时间戳是秒级别，1年要24位，两年要25位.....
自增序列，6万QPS要16位，10万要17位...
剩下20－24位，百万分之一到一千六百万分之一的重复率，然后把网卡Mac＋进程号拼在一起再hash，取结果32个bit的后面20或24个bit。但假如这个标识字段重复了，后面时间戳和自增序列也很容易重复，不停的重复。
思路二，使用ZK 或 mysql 或 redis来自增管理机器＋进程标识号
如果机器＋进程标识字段只留了12位（4096），就要用ZK或etcd，线程启动时分配号码，当进程关闭了要回收这个号。
如果标示号的位数留得够多，比如有20位（一百万），那用redis或mysql来自增标识号最简单，每个进程启动时就去拿一个机器＋服务进程的标示号。
思路三，继续Random
继续拼了，直接拿JDK UUID.randomUUID()的低位long（按UUID规范，高位的long被置了4个默认值的bit，低位只被设置3个bit），或者不用UUID.randomUUID()了，直接SecureRandom.nextLong()，不浪费了作为默认值总是不变的那3个bit。
你猜我们最后选了哪种？